

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2024-02-03
 * Time: 13:43
 *
 * https://www.nowcoder.com/share/jump/7745334641706942049163
 */
public class BM65 {

    // 全局变量方便使用
    private String x;

    /**
     * @param i        起始位置坐标
     * @param j        起始位置坐标
     * @param position 记录方向的数组
     */
    private String ans(int i, int j, int[][] position) {
        String res = "";
        // 结束递归
        if (i <= 0 || j <= 0) {
            return res;
        }
        // 根据 position 的方向开始递归
        if (position[i][j] == 1) {
            // 左上
            res += ans(i - 1, j - 1, position);
            // 当前位置的字母相同，也需要拼接上
            res += x.charAt(i - 1);
        } else if (position[i][j] == 2) {
            // 左
            res += ans(i - 1, j, position);
        } else {
            // 上
            res += ans(i, j - 1, position);
        }
        return res;
    }


    public String LCS(String s1, String s2) {
        if (s1.isEmpty() || s2.isEmpty()) {
            return "-1";
        }
        int len1 = s1.length(), len2 = s2.length();
        // 仅需一个即可记录子序列
        x = s1;
        // 借用动态规划记录长度顺便记录字符的位置
        int[][] dp = new int[len1 + 1][len2 + 1];
        // 1 表示来自左上方 dp[i -1][j - 1]，
        // 2 表示来自左方 dp[i - 1][j]，
        // 3 表示来自上方 dp[i][j - 1]
        int[][] position = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    // 1 表示来自左上方
                    position[i][j] = 1;
                } else {
                    if (dp[i - 1][j] > dp[i][j - 1]) {
                        dp[i][j] = dp[i - 1][j];
                        // 2 表示来自左方
                        position[i][j] = 2;
                    } else {
                        dp[i][j] = dp[i][j - 1];
                        // 3 表示来自上方
                        position[i][j] = 3;
                    }
                }
            }
        }
        // 通过 position 数组记录的路径，获得字符串
        String res = ans(len1, len2, position);
        return res.isEmpty() ? "-1" : res;
    }
}
